package com.leecode.exercise;

import java.util.HashMap;
import java.util.Map;

/**
 * "无重复字符的最长子串"（Longest Substring Without Repeating Characters）是一个经典的滑动窗口问题。
 * 题目要求找到给定字符串中最长的子串，该子串中没有重复的字符。
 */
public class 滑动窗口_02_字符串无重复最大子串 {


    public static void main(String[] args) {
        String s = "abcaebcbb";
        int result = lengthOfLongestSubstring(s);
        System.out.println("无重复字符的最长子串长度为：" + result); //3
    }


    public static int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        int left = 0;
        int right = 0;
        int len = s.length();

        //最大子串
        Map<Character, Character> map = new HashMap<>();
        while (right < len) {
            char curr = s.charAt(right);

            //不重复，就继续往下遍历
            if(!map.containsKey(curr)){
                // 当前字符不在窗口中，扩大窗口右边界
                map.put(curr,curr);
                maxLength = Math.max(maxLength,right-left+1);
                right++;
            }

            //重复
            else{
                // 当前字符在窗口中，缩小窗口左边界
               map.remove(s.charAt(left));
               left++;
            }

        }
        return maxLength;
    }
}
